import functools
class Solution:
    def canSplitArray(self, nums, m: int) -> bool:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i] 
        @functools.cache
        def dfs(i, j):
            if i == j:
                return True
            else:
                flag = False
                for k in range(i, j):
                    if (i == k or prefix[k + 1] - prefix[i] >= m) and (j == k + 1 or prefix[j + 1]- prefix[k + 1] >= m):
                        flag |= dfs(i, k) & dfs(k + 1, j)
                return flag
        return dfs(0, n - 1) 
                    
data = Solution()
nums = [1, 2, 1, 1]
m = 4
print(data.canSplitArray(nums, m))
